package chapter2;

import java.util.List;

/**
 * 遗传算法
 */
public class GeneticAlgorithm {
    private int populationSize;

    /**
     * 变异概率
     */
    private double mutationRate;

    /**
     * 交叉概率
     */
    private double crossoverRate;

    /**
     * 精英个数，精英个数不会发生交叉变异，代代相传
     */
    private int elitismCount;

    public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) {
        this.populationSize = populationSize;
        this.mutationRate = mutationRate;
        this.crossoverRate = crossoverRate;
        this.elitismCount = elitismCount;
    }

    /**
     * 初始化种群
     *
     * @param chromosomeLength 染色体长度
     * @return population 初代种群
     */
    public Population initPopulation(int chromosomeLength) {
        // 初始化种群
        Population population = new Population(this.populationSize, chromosomeLength);
        return population;
    }

    /**
     * 计算个体适应度
     *
     * @param individual 个体
     * @return 个体适应度
     */
    public double calcFitness(Individual individual) {

        // 初始化
        int correctGenes = 0;

        // 循环计算个体的基因 1的个数
        for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
            // 找出1的位置，统计加1
            if (individual.getGene(geneIndex) == 1) {
                correctGenes += 1;
            }
        }

        // 计算适应度
        //适应度=1的个数/染色体长度
        double fitness = (double) correctGenes / individual.getChromosomeLength();

        // 存适应度
        individual.setFitness(fitness);

        return fitness;
    }

    /**
     * 计算种群的适应度
     * 这里计算种群的适应度时，会重算个体的适应度
     *
     * @param population 种群的适应度
     */
    public void evalPopulation(Population population) {
        double populationFitness = 0;

        // 对个体适应度求和是种群的适应度
        for (Individual individual : population.getIndividuals()) {
            populationFitness += calcFitness(individual);
        }
        population.setPopulationFitness(populationFitness);
    }

    /**
     * 检查种群是否满足终止条件
     * 这里的终止条件是个体满足适应度=1
     *
     * @param population
     * @return boolean
     */
    public boolean isTerminationConditionMet(Population population) {
        for (Individual individual : population.getIndividuals()) {
            if (individual.getFitness() == 1) {
                return true;
            }
        }
        return false;
    }

    /**
     * 选择父代
     * 轮盘选择
     *
     * @param population 种群
     * @return 个体
     */
    public Individual selectParent(Population population) {
        // 获取个体列表
        List<Individual> individuals = population.getIndividuals();

        // 旋转轮盘，实际上用的0~1的随机数*种群适应度
        double populationFitness = population.getPopulationFitness();
        double rouletteWheelPosition = Math.random() * populationFitness;

        // 轮盘得到一个值，遍历个体，个体累计适应度达到这个值时选中这个个体返回，若一直达不到，选最后一个个体
        double spinWheel = 0;
        for (Individual individual : individuals) {
            spinWheel += individual.getFitness();
            if (spinWheel >= rouletteWheelPosition) {
                return individual;
            }
        }
        return individuals.get(population.size() - 1);
    }

    /**
     * 交叉
     *
     * @param population The population to apply crossover to
     * @return The new population
     */
    public Population crossoverPopulation(Population population) {
        // 创建一个新种群
        Population newPopulation = new Population(population.size());

        //根据适应度循环
        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            //按适应度从大到小选择第一个父代
            Individual parent1 = population.getFittest(populationIndex);

            // 根据交叉率判断是否交叉，随机生成一个随机数，和交叉率比较，并且跳过指定的精英个数
            if (this.crossoverRate > Math.random() && populationIndex >= this.elitismCount) {
                // 根据染色体长度初始化子代
                Individual offspring = new Individual(parent1.getChromosomeLength());

                // 轮盘选择第二个父代
                Individual parent2 = selectParent(population);

                // 循环基因位点，若小于0.5，则基因来自适应度选择的parent1，若大于等于0.5，则基因来自轮盘选中的parent2
                for (int geneIndex = 0; geneIndex < parent1.getChromosomeLength(); geneIndex++) {
                    // 一半来自parent1，一半来自parent2
                    if (0.5 > Math.random()) {
                        offspring.setGene(geneIndex, parent1.getGene(geneIndex));
                    } else {
                        offspring.setGene(geneIndex, parent2.getGene(geneIndex));
                    }
                }

                // 新种群指定位置存子代信息
                newPopulation.addIndividual(offspring);
            } else {
                // 不交叉传给下一代
                newPopulation.addIndividual(parent1);
            }
        }

        return newPopulation;
    }

    /**
     * 执行种群变异
     *
     * @param population 种群
     * @return
     */
    public Population mutatePopulation(Population population) {
        // 初始化新种群
        Population newPopulation = new Population(this.populationSize);

        // 根据适应度循环
        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual individual = population.getFittest(populationIndex);

            // 遍历个体的基因值
            for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
                // 跳过指定的精英个数
                if (populationIndex > this.elitismCount) {
                    // 根据变异率判断是否变异
                    if (this.mutationRate > Math.random()) {
                        // 获取新的基因值
                        int newGene = 1;
                        if (individual.getGene(geneIndex) == 1) {
                            newGene = 0;
                        }
                        // 设置新的基因值
                        individual.setGene(geneIndex, newGene);
                    }
                }
            }

            // 设置新个体
            newPopulation.addIndividual(individual);
        }

        // 返回变异后的种群
        return newPopulation;
    }

}
